package 二叉树题目.判断是不是二叉搜索树;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static boolean isValidBST (TreeNode root,List<Integer> list) {
        // write code here
        int[] array = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            if(list.size() == 1){
                return true;
            }
            if (list.get(i)<list.get(i+1)){
                array[i] = list.get(i);
            }
            if (i+1 == list.size() - 1){
                array[i+1] = list.get(i+1);
                break;
            }
        }
        for (int i = 0; i < list.size(); i++) {
            if (array[i] != list.get(i)){
                return false;
            }
        }
        return true;
    }
    public static void inorder(TreeNode root, List<Integer> list){
        if (root == null){
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
//        node1.left = node2;
//        node1.right = node3;
        List<Integer> list = new ArrayList<>();
        inorder(node1,list);
        System.out.println(isValidBST(node1, list));
    }


    public boolean isValidBST2 (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int[] array = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            if(list.size() == 1){
                return true;
            }
            if (list.get(i) < list.get(i + 1)) {
                array[i] = list.get(i);
            }
            if (i + 1 == list.size() - 1) {
                array[i + 1] = list.get(i + 1);
                break;
            }
        }
        for (int i = 0; i < list.size(); i++) {
            if (array[i] != list.get(i)) {
                return false;
            }
        }
        return true;
    }





}
